home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 5746 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.1 KB  |  60 lines
  1. Path: po.CWRU.Edu!mab22
  2. From: mab22@po.CWRU.Edu (Michael A. Balfour)
  3. Newsgroups: comp.lang.c
  4. Subject: Perfect Hashing
  5. Date: 21 Feb 1996 00:30:18 GMT
  6. Organization: Case Western Reserve University, Cleveland, OH (USA)
  7. Message-ID: <4gdp2q$hd4@madeline.INS.CWRU.Edu>
  8. Reply-To: mab22@po.CWRU.Edu (Michael A. Balfour)
  9. NNTP-Posting-Host: kanga.ins.cwru.edu
  10.  
  11.  
  12. Hi!
  13.  
  14. I'm looking for a perfect hashing function.
  15.  
  16. That being said, let me explain a little further before the "You can't
  17. have a compressive perfect hashing function over all strings" starts.
  18.  
  19. I'm reading in a series of strings (among other things) from sets of
  20. files.  I'd like to perfectly hash all of the strings for each file.
  21. Each string is a max of 50 characters, and each file contains from
  22. 1-3000 strings or so, and each string is guaranteed to be unique.  It
  23. seems that perfect hashing should be possible given that I have the
  24. entire set of strings to work on at one time, but on the other hand I
  25. only have this set available at runtime.  My idea was to have a hashing
  26. function similar to:
  27.  
  28. long hash(char *string,long magicNumber,long numberOfStrings)
  29. {
  30.     long i=0;
  31.     char *p;
  32.  
  33.     for (p=string;*p!='\0';++p)
  34.         i+=(*p)*magicNumber;
  35.     return (i%numberOfStrings);
  36. }
  37.  
  38. where magicNumber would be some number computed for each file (and could
  39. possibly even be stored in the file), and numberOfStrings is of course
  40. the number of strings in the file, so that my hash function returns a
  41. number from 0-(numberOfStrings-1), suitable for array indexing.
  42.  
  43. Will my approach work?  How do I compute the magic number?
  44.  
  45. The reason I'm looking for a perfect hash, as opposed to a pretty good
  46. hash, is so that I don't even need to store the strings in memory.  I
  47. would just be able to index directly into an array which contains all of
  48. the other data I'm reading in.  If this approach won't work, does
  49. anybody have any other suggestions?
  50.  
  51. Thank you for your time,
  52.  
  53. Mike Balfour
  54.  
  55. -- 
  56. ----------------------------------+--------------------------------
  57. Mike Balfour, Partner             | BS/MS Graduate - ECMP
  58. Overload Engineering              | Case Western Reserve University
  59. "New Ideas for a Brighter Future" | Cleveland, OH
  60.